package Algorithm.array;

/**
 * @Desc:   寻找一个数（基本的二分搜索）
 *          即搜索一个数，如果存在，返回其索引，否则返回 -1
 *          给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
 *          写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 * @author: cww
 * @DateTime: 2020-06-08 0:45
 */

public class BinarySearch {

    public static void main(String[] args) {
        int[] i = new int[]{-5,8,8,11,21,26,28};
        System.out.println(left_bound(i, 8));
    }

    public static int binarySearch(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        while (left <= right){
            int mid = left + (right - left)/2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = left + mid + 1;
            else if (nums[mid] > target) right = right - mid -1;
        }
        return -1;
    }

    /**
     * 寻找左侧边界的二分查找
     * 有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 1
     * @param nums
     * @param target
     * @return
     */
    public static int left_bound(int[] nums, int target) {
        int left =0,right=nums.length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(nums[mid]>target){
                right = mid -1;
            } else if(nums[mid]<target){
                left = mid +1;
            } else if(nums[mid]==target){
                right = mid-1;
            }
        }
        if(left>nums.length||nums[left]!=target) return -1;
        return left;
    }

    /**
     * 寻找右侧边界的二分查找
     * @param nums
     * @param target
     * @return
     */
    public static int right_bound(int[] nums, int target){
        int left = 0,right = nums.length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if (nums[mid]==target){
                left = mid +1;
            } else if (nums[mid]<target){
                left = mid+1;
            }else if (nums[mid]>target){
                right  = mid-1;
            }
        }
        if (right<0||nums[right]!=target) return -1;

        return right;
    }


}
